package main

import "fmt"

//#link: https://leetcode-cn.com/problems/stone-game/
func main() {
	piles := []int{5, 3, 4, 5}
	fmt.Println(stoneGame(piles))
}

func stoneGame(piles []int) bool {
	//若拿了行头，则第二人可以拿第二个或最后一个
	dp := make([][]int, len(piles))
	for i := range dp {
		dp[i] = make([]int, len(piles))
		dp[i][i] = piles[i]
	}

	for i := len(piles) - 2; i >= 0; i-- {
		for j := i + 1; j < len(piles); j++ {
			dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])
		}
	}
	return dp[0][len(piles)-1] > 0
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
